/**************************************************************************************************
 *
 *	XCS Crowd Simulation Software
 *	Author: Scott Bevin
 *	Web: www.gameXcore.co.uk
 *	Email: scott@gameXcore.co.uk
 *	All code (c)2010 Scott Bevin, all rights reserved.
 *	
 *	This software is part of the disssertation work entitled "Real time crowd simulations incorporating individual
 *	agent personality models and group interactions" submitted to The University of Bolton by Scott Bevin in partial
 *	fulfilment of the requirements of The University of Bolton for the degree of Bachelor of Science in May 2010.
 *	
 **************************************************************************************************/

 /************************************************************************

 This file is part of "Real time crowd simulations incorporating individual agent personality models and group interactions".

 "Real time crowd simulations incorporating individual agent personality 
 models and group interactions" is free software: you can redistribute 
 it and/or modify it under the terms of the GNU General Public License 
 as published by the Free Software Foundation, either version 3 of the 
 License, or (at your option) any later version.

 "Real time crowd simulations incorporating individual agent personality models and group interactions" is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with "Real time crowd simulations incorporating individual agent personality models and group interactions".  
 If not, see <http://www.gnu.org/licenses/>.

************************************************************************/

// All code (c)2010 Scott Bevin, all rights reserved.

#ifndef PRIORITYQUEUE_H
#define PRIORITYQUEUE_H


#include <ostream>
#include <vector>
#include <cassert>

namespace XF
{
	//----------------------- Swap -------------------------------------------
	//
	//  used to swap two values
	//------------------------------------------------------------------------
	template<class T>
	void Swap(T &a, T &b)
	{
	  T temp = a;
	  a = b;
	  b = temp;
	}

	//-------------------- ReorderUpwards ------------------------------------
	//
	//  given a heap and a node in the heap, this function moves upwards
	//  through the heap swapping elements until the heap is ordered
	//------------------------------------------------------------------------
	template<class T>
	void ReorderUpwards(std::vector<T>& heap, int nd)
	{
	  //move up the heap swapping the elements until the heap is ordered
	  while ( (nd>1) && (heap[nd/2] < heap[nd]))
	  {
		Swap(heap[nd/2], heap[nd]);

		nd /= 2;
	  }
	}

	//--------------------- ReorderDownwards ---------------------------------
	//
	//  given a heap, the heapsize and a node in the heap, this function
	//  reorders the elements in a top down fashion by moving down the heap
	//  and swapping the current node with the greater of its two children
	//  (provided a child is larger than the current node)
	//------------------------------------------------------------------------
	template<class T>
	void ReorderDownwards(std::vector<T>& heap, int nd, int HeapSize)
	{
	  //move down the heap from node nd swapping the elements until
	  //the heap is reordered
	  while (2*nd <= HeapSize)
	  {
		int child = 2 * nd;

		//set child to largest of nd's two children
		if ( (child < HeapSize) && (heap[child] < heap[child+1]) )
		{
		  ++child;
		}

		//if this nd is smaller than its child, swap
		if (heap[nd] < heap[child])
		{
		  Swap(heap[child], heap[nd]);

		  //move the current node down the tree
		  nd = child;
		}

		else
		{
		  break;
		}
	  }
	}



	//--------------------- PriorityQ ----------------------------------------
	//
	//  basic heap based priority queue implementation
	//------------------------------------------------------------------------
	template<class T>
	class PriorityQ
	{
	private:

	  std::vector<T>  m_Heap;

	  int             m_iSize;

	  int             m_iMaxSize;

	  //given a heap and a node in the heap, this function moves upwards
	  //through the heap swapping elements until the heap is ordered
	  void ReorderUpwards(std::vector<T>& heap, int nd)
	  {
		//move up the heap swapping the elements until the heap is ordered
		while ( (nd>1) && (heap[nd/2] < heap[nd]))
		{
		  Swap(heap[nd/2], heap[nd]);

		  nd /= 2;
		}
	  }

	  //given a heap, the heapsize and a node in the heap, this function
	  //reorders the elements in a top down fashion by moving down the heap
	  //and swapping the current node with the greater of its two children
	  //(provided a child is larger than the current node)
	  void ReorderDownwards(std::vector<T>& heap, int nd, int HeapSize)
	  {
		//move down the heap from node nd swapping the elements until
		//the heap is reordered
		while (2*nd <= HeapSize)
		{
		 int child = 2 * nd;

		  //set child to largest of nd's two children
		  if ( (child < HeapSize) && (heap[child] < heap[child+1]) )
		 {
			++child;
		  }

		  //if this nd is smaller than its child, swap
		  if (heap[nd] < heap[child])
		  {
			Swap(heap[child], heap[nd]);

			//move the current node down the tree
			nd = child;
		  }
	  
		  else
		  {
			break;
		  }
		}
	  }

	public:

	  PriorityQ(int MaxSize):m_iMaxSize(MaxSize), m_iSize(0)
	  {
		m_Heap.assign(MaxSize+1, T());
	  }

	  bool empty()const{return (m_iSize==0);}

	  //to insert an item into the queue it gets added to the end of the heap
	  //and then the heap is reordered
	  void insert(const T item)
	  {

		assert (m_iSize+1 <= m_iMaxSize);

		++m_iSize;

		m_Heap[m_iSize] = item;

		ReorderUpwards(m_Heap, m_iSize);
	  }

	  //to get the max item the first element is exchanged with the lowest
	  //in the heap and then the heap is reordered from the top down. 
	  T pop()
	  {
		Swap(m_Heap[1], m_Heap[m_iSize]);

		ReorderDownwards(m_Heap, 1, m_iSize-1);

		return m_Heap[m_iSize--];
	  }

	  //so we can take a peek at the first in line
	  const T& Peek()const{return m_Heap[1];}
	};

	//--------------------- PriorityQLow -------------------------------------
	//
	//  basic 2-way heap based priority queue implementation. This time the priority
	//  is given to the lowest valued key
	//------------------------------------------------------------------------
	template<class T>
	class PriorityQLow
	{
	private:

	  std::vector<T>  m_Heap;

	  int             m_iSize;

	  int             m_iMaxSize;

	  //given a heap and a node in the heap, this function moves upwards
	  //through the heap swapping elements until the heap is ordered
	  void ReorderUpwards(std::vector<T>& heap, int nd)
	  {
		//move up the heap swapping the elements until the heap is ordered
		while ( (nd>1) && (heap[nd/2] > heap[nd]))
		{
		  Swap(heap[nd/2], heap[nd]);

		  nd /= 2;
		}
	  }

	  //given a heap, the heapsize and a node in the heap, this function
	  //reorders the elements in a top down fashion by moving down the heap
	  //and swapping the current node with the smaller of its two children
	  //(provided a child is larger than the current node)
	  void ReorderDownwards(std::vector<T>& heap, int nd, int HeapSize)
	  {
		//move down the heap from node nd swapping the elements until
		//the heap is reordered
		while (2*nd <= HeapSize)
		{
		 int child = 2 * nd;

		  //set child to largest of nd's two children
		  if ( (child < HeapSize) && (heap[child] > heap[child+1]) )
		 {
			++child;
		  }

		  //if this nd is smaller than its child, swap
		  if (heap[nd] > heap[child])
		  {
			Swap(heap[child], heap[nd]);

			//move the current node down the tree
			nd = child;
		  }
	  
		  else
		  {
			break;
		  }
		}
	  }

	public:

	  PriorityQLow(int MaxSize):m_iMaxSize(MaxSize), m_iSize(0)
	  {
		m_Heap.assign(MaxSize+1, T());
	  }

	  bool empty()const{return (m_iSize==0);}

	  //to insert an item into the queue it gets added to the end of the heap
	  //and then the heap is reordered
	  void insert(const T item)
	  {
		assert (m_iSize+1 <= m_iMaxSize);

		++m_iSize;

		m_Heap[m_iSize] = item;

		ReorderUpwards(m_Heap, m_iSize);
	  }

	  //to get the max item the first element is exchanged with the lowest
	  //in the heap and then the heap is reordered from the top down. 
	  T pop()
	  {
		Swap(m_Heap[1], m_Heap[m_iSize]);

		ReorderDownwards(m_Heap, 1, m_iSize-1);

		return m_Heap[m_iSize--];
	  }

	  //so we can take a peek at the first in line
	  const T& peek()const{return m_Heap[1];}
	};

	//----------------------- IndexedPriorityQLow ---------------------------
	//
	//  Priority queue based on an index into a set of keys. The queue is
	//  maintained as a 2-way heap.
	//
	//  The priority in this implementation is the lowest valued key
	//------------------------------------------------------------------------
	template<class KeyType>
	class IndexedPriorityQLow
	{
	private:

	  std::vector<KeyType>&  m_vecKeys;

	  std::vector<int>       m_Heap;
	 
	  std::vector<int>       m_invHeap;

	  int                    m_iSize,
							 m_iMaxSize;

	  void Swap(int a, int b)
	  {
		int temp = m_Heap[a]; m_Heap[a] = m_Heap[b]; m_Heap[b] = temp;

		//change the handles too
		m_invHeap[m_Heap[a]] = a; m_invHeap[m_Heap[b]] = b;
	  }

	  void ReorderUpwards(int nd)
	  {
		//move up the heap swapping the elements until the heap is ordered
		while ( (nd>1) && (m_vecKeys[m_Heap[nd/2]] > m_vecKeys[m_Heap[nd]]) )
		{      
		  Swap(nd/2, nd);

		  nd /= 2;
		}
	  }

	  void ReorderDownwards(int nd, int HeapSize)
	  {
		//move down the heap from node nd swapping the elements until
		//the heap is reordered
		while (2*nd <= HeapSize)
		{
		  int child = 2 * nd;

		  //set child to smaller of nd's two children
		  if ((child < HeapSize) && (m_vecKeys[m_Heap[child]] > m_vecKeys[m_Heap[child+1]]))
		  {
			++child;
		  }

		  //if this nd is larger than its child, swap
		  if (m_vecKeys[m_Heap[nd]] > m_vecKeys[m_Heap[child]])
		  {
			Swap(child, nd);

			//move the current node down the tree
			nd = child;
		  }

		  else
		  {
			break;
		  }
		}
	  }


	public:
	  
	  //you must pass the constructor a reference to the std::vector the PQ
	  //will be indexing into and the maximum size of the queue.
	  IndexedPriorityQLow(std::vector<KeyType>& keys,
						  int              MaxSize):m_vecKeys(keys),
													m_iMaxSize(MaxSize),
													m_iSize(0)
	  {
		m_Heap.assign(MaxSize+1, 0);
		m_invHeap.assign(MaxSize+1, 0);
	  }

	  bool empty()const{return (m_iSize==0);}

	  //to insert an item into the queue it gets added to the end of the heap
	  //and then the heap is reordered from the bottom up.
	  void insert(const int idx)
	  {
		assert (m_iSize+1 <= m_iMaxSize);

		++m_iSize;

		m_Heap[m_iSize] = idx;

		m_invHeap[idx] = m_iSize;

		ReorderUpwards(m_iSize);
	  }

	  //to get the min item the first element is exchanged with the lowest
	  //in the heap and then the heap is reordered from the top down. 
	  int Pop()
	  {
		Swap(1, m_iSize);

		ReorderDownwards(1, m_iSize-1);

		return m_Heap[m_iSize--];
	  }

	  //if the value of one of the client key's changes then call this with 
	  //the key's index to adjust the queue accordingly
	  void ChangePriority(const int idx)
	  {
		ReorderUpwards(m_invHeap[idx]);
	  }
	};
}

#endif